package 动态规划专项训练.动态规划训练1;

/**55.跳跃游戏
 * 存在型动态规划
 * @author zx
 * @create 2022-03-30 16:39
 */
public class Num55{
    /**
     * @return 时间复杂度：O(N^2)，空间复杂度(数组大小)：O(N)
     */
    public boolean canJump(int[] nums) {
        if(nums.length == 0){
            return false;
        }
        int n = nums.length;
        boolean[] f = new boolean[n];
        //初始条件
        f[0] = true;
        for(int i = 1;i < n;i++){
            //规划最后一块石头之前的石头的跳法
            f[i] = false;//如果0 ~ i(倒数第二个石头)个石头中,有任意一个可以跳到最后一块石头,则置为true
            for(int j = 0;j < i;j++){
                if(f[j] && j + nums[j] >= i){
                    f[i] = true;
                    break;//如果某个石头可以跳到最后一个石头,就可以退出来了
                }
            }
        }
        return f[n - 1];
    }
}
